perm filename AI72.QUA[ESS,JMC]1 blob
sn#005567 filedate 1972-04-05 generic text, type T, neo UTF8
00000
00100
00200
00300
00400
00500
00600
00700
00800
00900 STANFORD UNIVERSITY
01000
01100
01200 COMPUTER SCIENCE DEPARTMENT
01300
01400
01500 April 1, 1972
01600
01700
01800
01900
02000
02100
02200
02300
02400
02500 Ph.D. QUALIFYING EXAMINATION
02600
02700
02800 Artificial Intelligence
02900
03000
03100
03200
03300
03400
03500
03600
03700 The examination will be open book. The first session will be from
03800 9:30 to 12:30 pm, and the second session will be from 1:30 to 4:30
03900 pm. No work on the examination will be done during the lunch break.
04000
00100 1. a. In terms of the quality of solutions found, and the
00200 efficiency with which solutions are produced, the Heuristic DENDRAL
00300 program is one of the most powerful heuristic programs in existence.
00400 What is the primary source of this problem-solving power?
00500
00600 b. In his paper on Heuristic Programming, subtitled "Ill-
00700 Structured Problems", Newell introduces concepts and terminology
00800 intended to categorize and describe heuristic programs. Use Newell's
00900 concepts and terminology to describe Heuristic DENDRAL.
01000
01100 c. What are the purposes of having a systematic generator
01200 (the DENDRAL algorithm) at the heart of Heuristic DENDRAL?
01300
01400 d. We use heuristic processes to achieve search reduction in
01500 administering the search for a solution to a problem. How does the
01600 heuristic process known as the Planner in Heuristic DENDRAL
01700 contribute its heuristic power to search reduction? Illustrate by
01800 making reference to some of the results in the results tables of the
01900 DENDRAL paper you were asked to read. From a heuristic search point
02000 of view, how does "planning" in DENDRAL differ from "planning" as
02100 this method has been discussed elsewhere in the A.I. literature (e.g.
02200 the Planning Method of GPS, Hewitt's Planner, Robot Planning)?
02300
02400 e. You were asked to read a paper by Amarel in which he
02500 disucsses representation of knowledge and shift of representation.
02600 How has this problem been studied in the context of the task
02700 environment of Heuristic DENDRAL? What are the results?
00100 2. The unbounded unit-preference strategy is: "compute the
00200 resolvents of all unit clauses with every clause before computing the
00300 resolvents of any pair of non-units".
00400
00500 The input clause strategy is: "compute the resolvents of a pair of
00600 clauses only if one of them is a member of the initial set of clauses
00700 (i.e. an axiom or the negation of the theorem)".
00800
00900 a. Give examples showing that both of these strategies are
01000 logically incomplete.
01100
01200
01300 A replacement rule of inference for equality may be defined
01400 as follows.
01500
01600 Let E be the equality predicate and s, t, u be terms. Let A
01700 and B be clauses with no variables in common such that A contains a
01800 positive equality atom, either A = E(s,t)∨A' or A=E(t,s)∨A', and a
01900 term u occurs at least once in B. (Note: u may occur as a subterm).
02000 Let s and u have a common substitution instance, and suppose that α a
02100 most general unifier such that sα=uα. Let B* be the result of
02200 replacing an occurrence of uα in Bα by tα. Let C be the clause
02300 A'α∨B*. Then C may be inferred by replacement from A into B. Denote
02400 the set of such inferences by P(A,B).
02500 If A and B have common variables, these must be eliminated by
02600 a change of variables before the rule is applied.
02700
02800
02900 b. For all A and B, is P(A,B)=P(B,A)? Prove your answer.
03000
03100
03200 c. Let A be E(f(x,g(x)),e) and B be E(f(x,x),e). Compute
03300 P(A,B) and P(B,A).
03400
03500
03600
03700 d. PROVE: For any C that can be inferred by replacement
03800 from A and B there is a C' satisfying (i) C' implies C, and (ii)
03900 C' is obtained by a sequence of resolutions from the set consisting
04000 of A, B, and the axioms for equality.
04100
04200
04300 [section (d) of this question was omitted from the actual examination
04400 on April 1, 1972]
00100 3. After reading the speech report for inspiration, you have
00200 accepted a consulting job with the linguistics department to predict
00300 the feasibility of a speech understanding system. You are given the
00400 following vocabulary and grammar. You want a computer to recognize
00500 semantically and syntactically legal sentences. The department did
00600 not specify the semantics but any reasonable assumptions will do.
00700
00800 The vocabulary is:
00900
01000 programs, monkeys, termites,
01100 search, climb, eat
01200 trees, bits, bananas
01300
01400 The grammar is:
01500
01600 S → SUBJECT VERB OBJECT
01700 SUBJECT → programs, monkeys, termites
01800 VERB → search, climb, eat
01900 OBJECT→ trees, bits, bananas
02000
02100 a. First, assume a probability of correct recognition of one of
02200 the vocabulary words, when isolated, to be .7. Suppose the lexical
02300 segmentation scheme is perfect. Without use of the grammar what
02400 correct string recognition rate (all words correct) might be
02500 expected on three-word strings?
02600
02700 b. Based on the results of the speech report how might the
02800 probability of word-confusion error depend on vocabulary size?
02900
03000 c. Make a reasonable assumption (either your answer to (2) or
03100 some other guess) of the effect of vocabulary size on recognition
03200 rate. State your assumption. Now, using the grammar, but still no
03300 semantics, what correct string recognition rate might be expected?
03400 (rough calculations are fine).
03500
03600 d. Specify your assumed semantically meaningful strings. Show
03700 precisely why the recognition rate is better. For extra credit
03800 calculate an expected correct 3-word string recognition rate using
03900 both syntax and semantics.
04000
04100
00100 4. Consider the following variant of the missionary and
00200 cannibals problem:
00300
00400 "Three missionaries and three cannibals come to a river that
00500 they wish to cross. They find a boat that holds two people and can
00600 be rowed by one or two. However, if one person rows by himself, he
00700 will be too tired to row by himself again. Besides that, if the
00800 cannibals ever outnumber the missionaries on either bank of the
00900 river, the missionaries will be eaten. How can they all safely cross
01000 the river?"
01100
01200 a. Write a LISP program to find a solution.
01300
01400 b. Write a micro-PLANNER program to find a solution.
01500
01600 c. Write a situation-calculus description of the situation
01700 and the effects of actions from which it follows that there is a
01800 solution. The "result" formalism of McCarthy and Hayes is
01900 recommended.
02000
02100 d. Discuss the problem of making a program that could go from
02200 the above English statement of the missionary and cannibals problem
02300 to a LISP program for doing the tree search. Would the PLANNER
02400 formalism or the McCarthy and Hayes formalism be suitable as
02500 intermediate steps. Why or why not? In so far as possible, divide
02600 the overall problem into sub-problems that might be solved
02700 independently.
02800
00100 5. One of the central problems in the recognition of scenes
00200 involving plane-bounded objects is the segmentation problem. Falk,
00300 in his thesis, suggests improvements to Guzman's algorithm. Describe
00400 Guzman's and Falk's algrorithms. Give an example different from
00500 those in Falk's thesis where Guzman's fails and Falk's succeeds.
00600 Give an example where they both fail.
00700
00800 Extra credit:
00900 a. Extend Falk's algorithm to cover the case you presented
01000 above. If the new algorithm doesn' cover all cases, find a counter-
01100 example.
01200
01300 b. Discuss the segmentation problem for curved objects.